package leetcode.all;

public class Solution75 {

    public void sortColors(int[] nums) {

        int n = nums.length;
        int tail = 0;
        for (int i = 0; i < n; i++) {
            if(nums[i]==0){
                swap(nums,tail,i);
                tail++;
            }
        }
        for (int i = tail; i < n; i++) {
            if(nums[i]==1){
                swap(nums,tail,i);
                tail++;
            }
        }
    }

    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //partition规定
    //[0,p0) 0
    //[p0,i) 1
    //(p2,len-1] 2
    public void sortColors1(int[] nums) {
        int p0 = 0, p2 = nums.length-1, i = 0;
        while (i<=p2){
            if(nums[i]==0){
                swap(nums,i++,p0++);
            }else if(nums[i]==2){
                swap(nums,i,p2--);
            }else {
                i++;
            }
        }
    }

    public static void main(String[] args) {

        int[] nums = {2,0,2,1,1,0};

        Solution75 s = new Solution75();

        s.sortColors1(nums);
    }
}
